﻿#include <iostream>
#include <unordered_map>

using namespace std;

#define MIN(a,b) (a<b?a:b)
#define INVALID_MIN 0xffff

static int minLenOfContainsAllCharacters(const char* str, const char* subStr)
{
	if (!str || !subStr) return 0;

	auto strSize = strlen(str);
	auto subSize = strlen(subStr);
	if (strSize ==0 || subSize == 0) return 0;

	int all = subSize;
	char cur;
	unordered_map<char, int> subCharMap;
	for (int i = 0; i < subSize; i++)
	{
		cur = subStr[i];
		++subCharMap[cur];
	}

	// 左闭右开
	int l = -1;
	int r = 0;
	int minLength = INVALID_MIN;
	bool judgeR = true;
	int nowLength;
	while (l < r && r <= strSize)
	{
		if (r == 0)
		{
			++r;
			judgeR = true;
			continue;
		}

		if (judgeR)
		{
			cur = str[r - 1];
			if (subCharMap.find(cur) != subCharMap.end())
			{
				--subCharMap[cur];
				if (subCharMap[cur] >= 0)
				{
					--all;
				}

				if (all == 0)
				{
					judgeR = false;
					nowLength = l == -1 ? (r - l - 1) : (r - l);
					minLength = MIN(minLength, nowLength);
					if (minLength == subSize)
					{
						return subSize;
					}

					++l;
				}
				else
				{
					++r;
				}
			}
			else
			{
				++r;
			}
		}
		else
		{
			cur = str[l];
			if (subCharMap.find(cur) != subCharMap.end())
			{
				++subCharMap[cur];
				if (subCharMap[cur] > 0)
				{
					++all;
				}

				if (all > 0)
				{
					judgeR = true;
					++r;
				}
				else
				{
					++l;
					nowLength = r - l;
					minLength = MIN(minLength, nowLength);
					if (minLength == subSize)
					{
						return subSize;
					}
				}
			}
			else
			{
				++l;
				nowLength = r - l;
				minLength = MIN(minLength, nowLength);
				if (minLength == subSize)
				{
					return subSize;
				}
			}
		}
	}

	return minLength == INVALID_MIN ? 0 : minLength;
}

/**
 * 给定字符串str1和str2, 求str1的子串中含有str2所有字符的最小子串长度
 * 
 * 举例:
 * str1="abcde", str2="ac"
 * 因为"abc"包含str2所有的字符，并且在满足这一条件的str1的所有子串中，"abc"是最短的，返回3.
 * str1="12345", str2="344"
 * 最小包含子串不存在，返回0.
 * 
 * 思路:
 * 滑动窗口。
 * 
 * 举例: str1="aaaabbcacbba" str2="babca"
 * 先针对str2准备好各个字母的计数，和所有字符个数:
 * a:2 (需要2个a)
 * b:2 (需要2个b)
 * c:1 (需要1个c)
 * all:5 (总共需要5个字符)
 * 然后针对str1准备好窗口变量L和R，都指向str1的外面索引，-1.
 * 
 * step1:
 *  |a|aaabbcacbba
 * R=0, 包入1个a，故a:1 b:2 c:1 all:4
 * 
 * step2:
 *  |aa|aabbcacbba
 * R=1, 又包入1个a，故a:0 b:2 c:1 all:3
 * 
 * step3:
 *  |aaa|abbcacbba
 * R=2, 又包入1个a，故a:-1 b:2 c:1 all:3. a是多余的，并没有减少剩余需求字符的个数
 * 
 * step4:
 *  |aaaa|bbcacbba
 * R=3, 又包入1个a，故a:-2 b:2 c:1 all:3.
 * 
 * step5:
 *  |aaaab|bcacbba
 * R=4, 包入1个b，故a:-2 b:1 c:1 all:2
 * 
 * step6:
 *  |aaaabb|cacbba
 * R=5, 又包入1个b，故a:-2 b:0 c:1 all:1
 * 
 * step7:
 *  |aaaabbc|acbba
 * R=6, 包入1个c，故a:-2 b:0 c:0 all:0. all到0了，说明目前的窗体中已经包含了所有需要的字符，当前L=-1，R=6，子串长度=7. 接下来移动L, 看能否让满足所有需要字符串的子串长度更小。
 * 
 * step8:
 *  a|aaabbc|acbba
 * L=0, 排除1个a，故a:-1 b:0 c:0 all:0. all还是0，说明目前的窗体中已经包含了所有需要的字符，当前L=0，R=6，子串长度=6. 接下来移动L, 看能否让满足所有需要字符串的子串长度更小。
 * 
 * step9：
 *  aa|aabbc|acbba
 * L=1, 又排除1个a，故a:0 b:0 c:0 all:0. all还是0，说明目前的窗体中已经包含了所有需要的字符，当前L=1，R=6，子串长度=5. 接下来移动L, 看能否让满足所有需要字符串的子串长度更小。
 * 
 * step10:
 *  aaa|abbc|acbba
 * L=2, 又排除1个a，故a:1 b:0 c:0 all:1. all大于0，不满足含有所有字符的要求，所以接下来要移动R，直到all==0, 然后再右移L，看能否让满足所有需要字符串的子串长度更小。
 * 
 * ...
 * 
 */
int main_minLengthOfContainsAllCharactersOfSubString()
{
	char str[] = "abcde";
	char subStr[] = "bcd";
	int minLen = minLenOfContainsAllCharacters(str, subStr);
	printf("%d", minLen);
	return 0;
}